#include <stdlib.h>
#include <stdio.h>

typedef char DataType;
#define ok 0
#define ERROR 1
typedef struct Node 
{
	DataType data;/*数据域*/
	struct Node *leftChild;/*左子树指针*/
	struct Node *rightChild;/*右子树指针*/
} BiTreeNode;/*结点的结构体定义*/

// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
int _create_tree(BiTreeNode **root_pp,char * pre_order_seq,int *current_index){
	int status_sub_tree;
	
	if(pre_order_seq[*current_index] == '\0'){
		//TODO
		(*root_pp) = NULL;
		return ok;
	}
	if(pre_order_seq[*current_index] == '#'){
		*root_pp = NULL;
		//需要消耗掉这个#字符，因此*current-indez 需要+1
		*current_index += 1;
		return ok;
	}
	(*root_pp)= (BiTreeNode*)malloc(sizeof(BiTreeNode));
	if(!(*root_pp)){
		printf("failed to allocate memory,now exit()");
		return ERROR;
	}
	(*root_pp)->data = pre_order_seq[*current_index];
	*current_index += 1;
	status_sub_tree = _create_tree(&((*root_pp)->leftChild),pre_order_seq, current_index);
	if(status_sub_tree == ERROR){ 
		return status_sub_tree;
	}
	status_sub_tree = _create_tree(&((*root_pp))->rightChild,pre_order_seq,current_index);
	if(status_sub_tree == ERROR){
		return status_sub_tree;
	}
	return ok;
}
void create_tree(BiTreeNode ** root_pp, char * pre_order_seq,int num_elements) {
	int num_scanned_chars=0;
	_create_tree(root_pp, pre_order_seq,&num_scanned_chars);
	num_elements = num_scanned_chars;
	//	num_scanned_chars num_elements
}

//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode *t, void visit(DataType item))
{
	if(t == NULL){
		return;
	}
	visit(t->data);
	pre_order_traverse(t->leftChild,visit);
	pre_order_traverse(t->rightChild,visit);
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item))
{
	if(t == NULL){
		return;
	}
	
	in_order_traverse(t->leftChild,visit);
	visit(t->data);
	in_order_traverse(t->rightChild,visit);
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item))
{
	if(t == NULL){
		return;
	}
	
	post_order_traverse(t->leftChild,visit);
	
	post_order_traverse(t->rightChild,visit);
	visit(t->data);
}

// 可以无需更改本函数的实现
void visit(DataType item)
{
	printf("%c ", item);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode * search(BiTreeNode *root, DataType x)//我这里把find设置为null所以一直为空指针！！！
{
	BiTreeNode *find=NULL;
	find = root;
	
	if(find == NULL){
		return find;
	}
	if(find->data == x){
		return find;
	}
	if(search(find->leftChild,x)){
		find=search(find->leftChild,x);
		return find;
	}
	if(search(find->rightChild,x)){
		find=search(find->rightChild,x);
		return find;
	}
	return NULL;
}

// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root)
{
	if(root != NULL){
		if((*root)->leftChild != NULL){
			destroy(&(*root)->leftChild);
		}
		if((*root)->rightChild!= NULL){
			destroy(&(*root)->leftChild);
		}
		root = NULL;
	}
}
int main(){
	char *a=NULL;
	char s[]="ABC##DE#G##F###";
	int count=0;
	BiTreeNode *root=NULL;
	BiTreeNode *find=NULL;
	a = s;
	/*while(*a){
printf("%c",*a);
a++;
}*/
	create_tree(&root,a,count);
	//_create_tree(&root,a,&count);
	//pre_order_traverse(root,visit);
	//in_order_traverse(root,visit);
	//post_order_traverse(root,visit);
	find=search(root,'F');
	if(find == NULL){
		printf("无元素");
	}else{
		printf("%c",(find->data));
	}
	destroy(&root);
	
	
	//printf("%c",(root->data));
	system("pause");
}
/*
pre_order_seq这个东西没有被引用到！！！
*/
